#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class Solution {
public:
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.size() == 0) return 0;
    
        map<int, char> myMap;
        for (int i = 1; i <= 26; i++)
            myMap[i] = 'A' + i-1;
        
        if (s.size() == 1 && myMap.count(s[0] - '0') != 0)  return 1;
        if (s.size() == 1 && myMap.count(s[0] - '0') == 0)  return 0;
         
        int a = 1, b = 1;
        if ( myMap.count(s[0] - '0') == 0) return 0;
      //  else b = 1;
        for (int i = 1; i < s.size(); i++) {
            int c = 0;
            int num = 10*(s[i-1] - '0') + (s[i]-'0');
            if (s[i-1] != '0' && myMap.count(num) != 0) c += a;
            if (myMap.count(s[i]-'0') != 0) c += b;
            a = b;
            b = c;            
        }
        return b;
    }
};


//better code
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s.size() == 0) return 0;
    
        vector<int> dp(s.size() +1, 0);
        dp[s.size()] = 1;
        
        for (int i = s.size()-1; i >= 0; i--) {
            if (s[i] != '0') {
                dp[i] = dp[i+1];
                if (i < s.size()-1 && (10*(s[i] - '0') + (s[i+1] - '0') <= 26))
                    dp[i] += dp[i+2];
            }
        }
         
        return dp[0];
    }


int main(int argc, char **argv)
{

    cout << "-----------------Test 1--------------------" << endl;


    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
